package leetcode.动态规划;
/*
通过分析，设节点为n的树的种类有f(n)种。则，以总节点数n=3为例，其种类总数可以认为是以下三种情况的种类数的和：
（1）以1为根节点，左子树0个节点，右子树2个节点：此时种类数=f(0)*f(2)
（2）以2为根节点，左子树1个节点，右子树1个节点，此时种类数=f(1)*f(1)
（3）以3为根节点，左子树2个节点，右子树1个节点：此时种类数=f(2)*f(0)
总节点数n=3的BST的种类数为，f(0)*f(2) + f(1)*f(1) + f(2)*f(0)。

由上面可以看出，每个小公式里的小括号里的数字之和都为n-1。到此，发现规律：总节点数为n的二叉搜索树的种类数为：
f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-1)*f(0)

里面的各项f(·)均可由子结果直接查表得到，因此采用动态规划解法。

 */
public class leetcode96 {
    public int numTrees(int n) {
        int[] res=new int[n+4];
        res[0]=1;
        res[1]=1;
        res[2]=2;
        for(int i=3;i<=n;i++){
            for(int j=0;j<i;j++){
                res[i] += res[j]*res[i-j-1];
            }
        }
        return res[n];

    }
}

